package com.hardy.newSolutionAlgorithm;

/**
 * Author: fuxh3@lenovo.com
 * Date: Created in 2017/11/15 0015
 *
 * 插入排序算法
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] nums = {4,3,2,5,7,8,8,12,34,45,67,12,32};
        method1(nums);
        for (int num:nums){
            System.out.println(num);
        }
    }
    public static void method1(int[] nums){
        int n=nums.length;
        for (int i=1;i<n;i++){
            int x = nums[i];
            int j = i-1;
            while (j>=0&&x<nums[j]){
                nums[j+1]=nums[j];
                j=j-1;
            }
            nums[j+1]=x;
        }
    }

    public static void method2(int[] nums){
        int n = nums.length;
        for (int i=1;i<n;i++){
            int x = nums[i];
            int p = binary_search(nums,x);
            
        }
    }

    public static int binary_search(int[] nums,int x){
        int l=0;
        int r = nums.length;
        while (l<r){
            int m = l+(r-l)/2;
            if(nums[m]==x){
                return m;
            }else if (nums[m]<x){
                l=m+1;
            }else{
                r=m;
            }
        }
        return l;
    }
}
